package com.berchen.offer;

import com.berchen.test.ListNode;

public class Test18 {
    public static void main(String[] args) {

    }
    public void reorderList(ListNode head) {

        int size=size(head);
        if(size==0){
            return;
        }
        // 移动元素的个数  (size+1)/2 -1
        int count=(size+1)/2-1;
        // 不移动的元素个数 size-count
        int notCount=size-count;

        // 先遍历到结尾的地方
        ListNode temp=head;
        int ydCount=1;
        while (ydCount!=notCount){
            temp=temp.next;
            ydCount++;
        }

        // 将前后两段分开
        ListNode ydNode=temp.next;
        temp.next=null;


        // 反转后半段链表
        temp=ydNode;
        ydNode=null;
        while (temp.next!=null){
            if(ydNode==null){
                ydNode=temp;
            }else {

                ListNode temp1=temp;
                temp=temp.next;

            }
        }

        while (count>0){

            // 拿到第一个移动的元素
            ListNode ydTemp=ydNode;
            ydNode=ydNode.next;
            ydTemp.next=null;

            // 找到要移动的位置
            int dyCountTemp=1;
            temp=head;
            while (dyCountTemp!=count){
                temp=temp.next;
                dyCountTemp++;
            }


            // 移动
            ydTemp.next=temp.next;
            temp.next=ydTemp;



            count--;
        }
    }


    /**
     * 计算链表大小
     * @param head
     * @return
     */
    private int size(ListNode head){
        int count=0;
        if(head!=null){
            count=1;
            while (head.next!=null){

                count++;
            }
        }
        return count;
    }
}
